package 剑指offer;

import java.util.LinkedList;
import java.util.List;

/**
 * @description: 设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能
 * set(value, count)：将记录(value, count)插入该结构
 * get(value)：返回key对应的value值
 * [要求]
 * set和get方法的时间复杂度为O(1)
 * 某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。
 * 当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。
 * 若opt=1，接下来两个整数x, y，表示set(x, y)
 * 若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
 * 对于每个操作2，输出一个答案
 * @author: ywk
 * @date: 2020-11-08
 */
public class 设计LRU缓存结构 {
    /**
     * lru design
     *
     * @param operators int整型二维数组 the ops
     * @param k         int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU(int[][] operators, int k) {
        // write code here

        int resultLength = 0;
        for (int[] operator : operators) {
            if (operator[0] == 2) {
                resultLength++;
            }
        }
        int[] results = new int[resultLength];
        int index = 0;

        LruCache cache = new LruCache(k);
        List<Integer> resultList = new LinkedList<>();
        for (int[] operator : operators) {
            switch (operator[0]) {
                case 1:
                    cache.set(operator[1], operator[2]);
                    break;
                case 2:
                    Integer value = cache.get(operator[1]);
                    results[index++] = value == null ? -1 : value;
            }
        }
        return results;
    }


    class LruCache {
        private final int capacity;
        private final Node[] hashTable;
        private int nodeCount;
        private Node lruHead;
        private Node lruTail;
        private Node eliminateNode;

         class Node {
            int key;
            int value;
            Node hashLink;
            Node lruPrev;
            Node lruNext;
        }

        LruCache(int capacity) {
            if (capacity < 1) {
                throw new IllegalArgumentException();
            }
            this.capacity = capacity;
            this.hashTable = new Node[(int) (capacity / 0.75)];
        }

        public Integer set(int key, int value) {
            int index = hashIndex(key);
            Node node = hashTable[index];
            while (node != null && node.key != key) {
                node = node.hashLink;
            }

            if (node != null) {
                int oldValue = node.value;
                node.value = value;
                touch(node);
                return oldValue;
            }

            if (eliminateNode == null) {
                node = new Node();
            } else {
                node = eliminateNode;
                eliminateNode = null;
            }
            node.key = key;
            node.value = value;
            node.hashLink = hashTable[index];
            hashTable[index] = node;

            if (nodeCount++ == 0) {
                lruHead = node;
                lruTail = node;
            } else {
                node.lruPrev = lruTail;
                lruTail.lruNext = node;
                lruTail = node;
            }

            if (nodeCount > capacity) {
                eliminate();
            }

            return null;
        }

        public Integer get(int key) {
            int index = hashIndex(key);
            Node node = hashTable[index];
            while (node != null && node.key != key) {
                node = node.hashLink;
            }
            if (node == null) {
                return null;
            }

            touch(node);

            return node.value;
        }

        private void touch(Node node) {
            if (node.lruNext == null) {
                return;
            }

            if (node.lruPrev == null) {
                lruHead = node.lruNext;
                lruHead.lruPrev = null;
            } else {
                node.lruPrev.lruNext = node.lruNext;
                node.lruNext.lruPrev = node.lruPrev;
            }
            node.lruNext = null;
            node.lruPrev = lruTail;
            lruTail.lruNext = node;
            lruTail = node;
        }

        private void eliminate() {
            Node node = lruHead;
            if (node == null) {
                return;
            }
            lruHead = node.lruNext;
            lruHead.lruPrev = null;
            node.lruNext = null;

            int index = hashIndex(node.key);
            Node curr = hashTable[index];
            Node last = null;
            while (curr != null && curr != node) {
                last = curr;
                curr = curr.hashLink;
            }

            if (last == null) {
                hashTable[index] = node.hashLink;
            } else {
                last.hashLink = node.hashLink;
            }

            node.hashLink = null;
            eliminateNode = node;
            nodeCount--;
        }

        private int hashIndex(int key) {
            return (key < 0 ? (key == Integer.MIN_VALUE ? 0 : -key) : key) % hashTable.length;
        }

    }
}
